package Leetcode;

import java.util.HashMap;

public class problem14 {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0){
            return "";
        }
        if(strs.length == 1 || strs[0].length() == 0){
            return strs[0];
        }

        TrieTree t = new TrieTree();
        for(int i = 0; i < strs.length;i++){
            t.insert(strs[i],t);
        }
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while(true){
            if(t.getMap().size() != 1 || t.getMap().containsKey("0")){
                return sb.toString();
            }
            if(t.isWord){
                return sb.append(strs[0].charAt(i)).toString();
            }
            sb.append(strs[0].charAt(i));
            t = t.getMap().get(strs[0].charAt(i));
            i++;
        }

    }

    class TrieTree {
        private boolean isWord = false;
        private HashMap<Character, TrieTree> map = new HashMap<>();

        public void insert(String str , TrieTree trieTree){
            if(str == null || str.length() == 0){
                trieTree.map.put('0',trieTree);
                return;
            }

            char[] c = str.toCharArray();
            int i = 0;
            TrieTree cur = trieTree;
            while (i < c.length){
                if(!cur.map.containsKey(c[i])){
                    cur.map.put(c[i],new TrieTree());
                }
                if(i == c.length - 1){
                    cur.isWord = true;
                }
                cur = cur.map.get(c[i]);
                i++;
            }
        }

        public HashMap<Character, TrieTree> getMap() {
            return map;
        }
    }
}
